#define _CRT_SECURE_NO_WARNINGS 1
#include "Heap.h"

void heapInit(heap* pheap) {
	heapData* newHeap = (heapData*)malloc(sizeof(heapData) * 4);
	assert(newHeap);
	pheap->ph = newHeap;
	pheap->size = 0;
	pheap->capacity = 4;
}

void swap(heapData* n1, heapData* n2) {
	heapData s = *n1;
	*n1 = *n2;
	*n2 = s;
}

void heapPush(heap* pheap, heapData num) {
	assert(pheap);
	if (pheap->size == pheap->capacity) {
		heapData* newHeap = (heapData*)realloc(pheap->ph, sizeof(heapData)*pheap->capacity * 2);
		assert(newHeap);
		pheap->ph = newHeap;
		pheap->capacity *= 2;
	}
	pheap->ph[pheap->size] = num;
	pheap->size++;

	AdjustUp(pheap->ph, pheap->size - 1);
}

void heapPop(heap* pheap) {
	assert(pheap);
	assert(!heapEmpty(pheap));
	swap(&pheap->ph[0], &pheap->ph[pheap->size - 1]);
	pheap->size--;

	AdjustDown(pheap->ph, pheap->size, 0);
}

void AdjustUp(heapData* a, int child) {
	assert(a);
	int parent = (child - 1) / 2;
	while (child > 0) {
		if (a[child] > a[parent]) {
			swap(a + child, a + parent);
			child = parent;
			parent = (child - 1) / 2;
		}
		else{
			break;
		}
	}
}

void AdjustDown(heapData* a, int size, int parent) {
	assert(a);
	int child = parent * 2 + 1;
	while (child < size) {
		if (child + 1 < size && a[child] < a[child + 1]) {
			child += 1;
		}
		if (a[parent] < a[child]) {
			swap(a + parent, a + child);
			parent = child;
			child = parent * 2 + 1;
		}
		else{
			break;
		}
	}
}

int heapEmpty(heap* pheap) {
	assert(pheap);
	return pheap->size == 0;
}

heapData heapTop(heap* pheap) {
	assert(pheap);
	return pheap->ph[0];
}

int heapSize(heap* pheap) {
	assert(pheap);
	return pheap->size;
}

void heapDestory(heap* pheap) {
	assert(pheap);
	free(pheap->ph);
	pheap->ph = NULL;
}